0400. 第 N 位数字【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 数学

1. 📝 题目描述

• leetcode

给你一个整数 n，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

---

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

解释：
第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0，它是 10 的一部分。

---

提示：

• 1 <= n <= 2^31 - 1

2. 🎯 s.1 - 数学

c

int findNthDigit(int n) {
    long long digits = 1, start = 1, count = 9;
    while (n > digits * count) {
        n -= digits * count;
        digits++;
        start *= 10;
        count *= 10;
    }
    long long num = start + (n - 1) / digits;
    int idx = (n - 1) % digits;
    // 取第 idx 位数字
    for (int i = digits - 1 - idx; i > 0; i--) num /= 10;
    return num % 10;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var findNthDigit = function (n) {
  let digits = 1,
    start = 1,
    count = 9
  while (n > digits * count) {
    n -= digits * count
    digits++
    start *= 10
    count *= 10
  }
  const num = start + Math.floor((n - 1) / digits)
  const idx = (n - 1) % digits
  return parseInt(String(num)[idx])
}

py

class Solution:
    def findNthDigit(self, n: int) -> int:
        digits, start, count = 1, 1, 9
        while n > digits * count:
            n -= digits * count
            digits += 1
            start *= 10
            count *= 10
        num = start + (n - 1) // digits
        idx = (n - 1) % digits
        return int(str(num)[idx])

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(1)$

算法思路：

• 按位数分段：1 位数 9 个（2 位数 90 个，3 位数 900 个...）
• 确定 $n$ 落在哪个段，计算具体数字和其中的第几位